from typing import Optional, List
from icecream import ic


def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2),
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_length = 0
    end_index = 0
    for i in range(m):
        for j in range(n):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
                if max_length < dp[i + 1][j + 1]:
                    max_length = dp[i + 1][j + 1]
                    end_index = i
    ic(dp)
    return s1[end_index - max_length + 1: end_index + 1]


s1 = 'abcabcddsgh'
s2 = 'gh'
print(longest_common_substring(s1, s2))
